<!DOCTYPE html>
<html lang="zh-Hans">
<head>

    <!--[if lt IE 9]>
        <style>body {display: none; background: none !important} </style>
        <meta http-equiv="Refresh" Content="0; url=//outdatedbrowser.com/" />
    <![endif]-->

<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="format-detection" content="telephone=no" />
<meta name="author" content="Bingo" />



<meta name="description" content="本文转载自JustDoIT,感谢原作者。
概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[">
<meta property="og:type" content="article">
<meta property="og:title" content="线段树学习笔记-1-入门">
<meta property="og:url" content="http://blog.acbingo.cn/2015/08/13/线段树学习笔记/index.html">
<meta property="og:site_name" content="Bingo's Blog">
<meta property="og:description" content="本文转载自JustDoIT,感谢原作者。
概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[">
<meta property="og:image" content="http://images.cnitblog.com/blog/517264/201312/01204058-426dce8b8a05491b91edeba9ec2e4112.jpg">
<meta property="og:updated_time" content="2015-11-25T03:08:41.400Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="线段树学习笔记-1-入门">
<meta name="twitter:description" content="本文转载自JustDoIT,感谢原作者。
概述线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[">
<meta name="twitter:image" content="http://images.cnitblog.com/blog/517264/201312/01204058-426dce8b8a05491b91edeba9ec2e4112.jpg">

<link rel="apple-touch-icon" href= "/apple-touch-icon.png">


    <link rel="alternate" href="/atom.xml" title="Bingo&#39;s Blog" type="application/atom+xml">



    <link rel="shortcut icon" href="/favicon.png">





    <link href="//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.css" rel="stylesheet">



    <script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
    <link href="//cdn.bootcss.com/pace/1.0.2/themes/blue/pace-theme-minimal.css" rel="stylesheet">


<link rel="stylesheet" href="/css/style.css">



<link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">


<title>线段树学习笔记-1-入门 | Bingo&#39;s Blog</title>

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>

<script>
    var yiliaConfig = {
        fancybox: true,
        animate: false,
        isHome: false,
        isPost: true,
        isArchive: false,
        isTag: false,
        isCategory: false,
        fancybox_js: "//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.js",
        scrollreveal: "//cdn.bootcss.com/scrollReveal.js/3.1.4/scrollreveal.min.js",
        search: true
    }
</script>


    <script> yiliaConfig.jquery_ui = [false]; </script>



    <script> yiliaConfig.rootUrl = "\/";</script>






</head>
<body>
  <div id="container">
    <div class="left-col">
    <div class="overlay"></div>
<div class="intrude-less">
    <header id="header" class="inner">
        <a href="/" class="profilepic">
            <img src="/img/avatar.png" class="animated zoomIn">
        </a>
        <hgroup>
          <h1 class="header-author"><a href="/">Bingo</a></h1>
        </hgroup>

        
        <p class="header-subtitle">Here&#39;s My Second Brains</p>
        

        
            <form id="search-form">
            <input type="text" id="local-search-input" name="q" placeholder="search..." class="search form-control" autocomplete="off" autocorrect="off" searchonload="false" />
            <i class="fa fa-times" onclick="resetSearch()"></i>
            </form>
            <div id="local-search-result"></div>
            <p class='no-result'>No results found <i class='fa fa-spinner fa-pulse'></i></p>
        


        
            <div id="switch-btn" class="switch-btn">
                <div class="icon">
                    <div class="icon-ctn">
                        <div class="icon-wrap icon-house" data-idx="0">
                            <div class="birdhouse"></div>
                            <div class="birdhouse_holes"></div>
                        </div>
                        <div class="icon-wrap icon-ribbon hide" data-idx="1">
                            <div class="ribbon"></div>
                        </div>
                        
                        <div class="icon-wrap icon-link hide" data-idx="2">
                            <div class="loopback_l"></div>
                            <div class="loopback_r"></div>
                        </div>
                        
                        
                        <div class="icon-wrap icon-me hide" data-idx="3">
                            <div class="user"></div>
                            <div class="shoulder"></div>
                        </div>
                        
                    </div>
                    
                </div>
                <div class="tips-box hide">
                    <div class="tips-arrow"></div>
                    <ul class="tips-inner">
                        <li>菜单</li>
                        <li>标签</li>
                        
                        <li>友情链接</li>
                        
                        
                        <li>关于我</li>
                        
                    </ul>
                </div>
            </div>
        

        <div id="switch-area" class="switch-area">
            <div class="switch-wrap">
                <section class="switch-part switch-part1">
                    <nav class="header-menu">
                        <ul>
                        
                            <li><a href="/">主页</a></li>
                        
                            <li><a href="/archives/">所有文章</a></li>
                        
                            <li><a href="/tags/">标签云</a></li>
                        
                            <li><a href="http://acbingo.cn/">关于我</a></li>
                        
                        </ul>
                    </nav>
                    <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" href="/&#116;&#x66;&#117;&#116;&#121;&#x40;&#x71;&#113;&#46;&#99;&#111;&#109;" title="Email"></a>
                            
                                <a class="fa GitHub" href="https://github.com/ACBingo" title="GitHub"></a>
                            
                                <a class="fa 知乎" href="https://www.zhihu.com/people/li-bing-59-10" title="知乎"></a>
                            
                                <a class="fa StackOverflow" href="http://stackoverflow.com/users/6059386/acbingo" title="StackOverflow"></a>
                            
                        </ul>
                    </nav>
                </section>
                
                
                <section class="switch-part switch-part2">
                    <div class="widget tagcloud" id="js-tagcloud">
                        <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Android/">Android</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Array/">Array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hash-Table/">Hash Table</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/KMP/">KMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/LeetCode/">LeetCode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Linked-List/">Linked List</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Math/">Math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/STL/">STL</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/String/">String</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/android/">android</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/anroid/">anroid</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/books/">books</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/c/">c#</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/c/">c++</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cocos/">cocos</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cocos2dx/">cocos2dx</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/const/">const</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/coursera/">coursera</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/git/">git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/github/">github</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hdu/">hdu</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hexo/">hexo</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/markdown/">markdown</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/offer/">offer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/poj/">poj</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/shadowsocks/">shadowsocks</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/string/">string</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ubuntu/">ubuntu</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/uva/">uva</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/vim/">vim</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/二分/">二分</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/二叉树/">二叉树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/位运算/">位运算</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/其它/">其它</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/分治/">分治</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/动态规划/">动态规划</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/单调队列/">单调队列</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/回溯/">回溯</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/字符串/">字符串</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/字符串匹配/">字符串匹配</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/指针/">指针</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/排序/">排序</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/操作系统/">操作系统</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/数据结构/">数据结构</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/枚举/">枚举</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/树/">树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/算法/">算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/红黑树/">红黑树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/线段树/">线段树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/继承/">继承</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/编译原理/">编译原理</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/虚函数/">虚函数</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/逆序对/">逆序对</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/递归/">递归</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/链表/">链表</a></li></ul>
                    </div>
                </section>
                
                
                
                <section class="switch-part switch-part3">
                    <div id="js-friends">
                    
                      <a class="main-nav-link switch-friends-link" href="https://hexo.io">Hexo</a>
                    
                      <a class="main-nav-link switch-friends-link" href="https://pages.github.com/">GitHub</a>
                    
                      <a class="main-nav-link switch-friends-link" href="http://moxfive.xyz/">MOxFIVE</a>
                    
                    </div>
                </section>
                

                
                
                <section class="switch-part switch-part4">
                
                    <div id="js-aboutme">专注于前端</div>
                </section>
                
            </div>
        </div>
    </header>                
</div>
    </div>
    <div class="mid-col">
      <nav id="mobile-nav">
      <div class="overlay">
          <div class="slider-trigger"></div>
          <h1 class="header-author js-mobile-header hide"><a href="/" title="回到主页">Bingo</a></h1>
      </div>
    <div class="intrude-less">
        <header id="header" class="inner">
            <a href="/" class="profilepic">
                <img src="/img/avatar.png" class="animated zoomIn">
            </a>
            <hgroup>
              <h1 class="header-author"><a href="/" title="回到主页">Bingo</a></h1>
            </hgroup>
            
            <p class="header-subtitle">Here&#39;s My Second Brains</p>
            
            <nav class="header-menu">
                <ul>
                
                    <li><a href="/">主页</a></li>
                
                    <li><a href="/archives/">所有文章</a></li>
                
                    <li><a href="/tags/">标签云</a></li>
                
                    <li><a href="http://acbingo.cn/">关于我</a></li>
                
                <div class="clearfix"></div>
                </ul>
            </nav>
            <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" target="_blank" href="/&#116;&#x66;&#117;&#116;&#121;&#x40;&#x71;&#113;&#46;&#99;&#111;&#109;" title="Email"></a>
                            
                                <a class="fa GitHub" target="_blank" href="https://github.com/ACBingo" title="GitHub"></a>
                            
                                <a class="fa 知乎" target="_blank" href="https://www.zhihu.com/people/li-bing-59-10" title="知乎"></a>
                            
                                <a class="fa StackOverflow" target="_blank" href="http://stackoverflow.com/users/6059386/acbingo" title="StackOverflow"></a>
                            
                        </ul>
            </nav>
        </header>                
    </div>
    <link class="menu-list" tags="标签" friends="友情链接" about="关于我"/>
</nav>
      <div class="body-wrap"><article id="post-线段树学习笔记" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2015/08/13/线段树学习笔记/" class="article-date">
      <time datetime="2015-08-13T02:15:15.000Z" itemprop="datePublished">2015-08-13</time>
</a>


    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      线段树学习笔记-1-入门
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        

        
    <div class="article-tag tagcloud">
        <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/线段树/">线段树</a></li></ul>
    </div>

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
          
        <p>本文转载自<a href="http://www.cnblogs.com/TenosDoIt/p/3453089.html" target="_blank" rel="external">JustDoIT</a>,感谢原作者。</p>
<h1 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h1><p>线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。<br>线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。</p>
<h1 id="从一个例子理解线段树"><a href="#从一个例子理解线段树" class="headerlink" title="从一个例子理解线段树"></a>从一个例子理解线段树</h1><p>下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr[0…n-1]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。<br>对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。<br>另一种解法：使用一个二维数组来保存提前计算好的区间[i,j]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。<br>我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树</p>
<ul>
<li>叶子节点是原始组数arr中的元素</li>
<li>非叶子节点代表它的所有子孙叶子节点所在区间的最小值<br>例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr[0…5]内的最小值是1）：<br><img src="http://images.cnitblog.com/blog/517264/201312/01204058-426dce8b8a05491b91edeba9ec2e4112.jpg" alt=""><br>由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作：创建线段树、查询、节点更新 是如何运作的呢（以下所有代码都是针对求区间最小值问题）？<h2 id="创建线段树"><a href="#创建线段树" class="headerlink" title="创建线段树"></a>创建线段树</h2>对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树，我们也可以用数组来存储，下面的讨论及代码都是数组来存储线段树，节点结构如下（注意到用数组存储时，有效空间为2n-1,实际空间确不止这么多，比如上面的线段树中叶子节点1、3虽然没有左右子树，但是的确占用了数组空间，实际空间是满二叉树的节点数目,但是这个空间复杂度也是O(n)的)。<br>struct SegTreeNode<br>{<br>　　int val;<br>};<br>定义包含n个节点的线段树 SegTreeNode segTree[n]，segTree[0]表示根节点。那么对于节点segTree[i]，它的左孩子是segTree[2<em>i+1],右孩子是segTree[2</em>i+2]。<br>我们可以从根节点开始，平分区间，递归的创建线段树，线段树的创建函数如下：<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div></pre></td><td class="code"><pre><div class="line">const int MAXNUM = 1000;</div><div class="line">struct SegTreeNode</div><div class="line">&#123;</div><div class="line">    int val;</div><div class="line">&#125;segTree[MAXNUM*4];//定义线段树</div><div class="line"></div><div class="line">/*</div><div class="line">功能：构建线段树</div><div class="line">root：当前线段树的根节点下标</div><div class="line">arr: 用来构造线段树的数组</div><div class="line">istart：数组的起始位置</div><div class="line">iend：数组的结束位置</div><div class="line">*/</div><div class="line">void build(int root, int arr[], int istart, int iend)</div><div class="line">&#123;</div><div class="line">    if(istart == iend)//叶子节点</div><div class="line">        segTree[root].val = arr[istart];</div><div class="line">    else</div><div class="line">    &#123;</div><div class="line">        int mid = (istart + iend) / 2;</div><div class="line">        build(root*2+1, arr, istart, mid);//递归构造左子树</div><div class="line">        build(root*2+2, arr, mid+1, iend);//递归构造右子树</div><div class="line">        //根据左右子树根节点的值，更新当前根节点的值</div><div class="line">        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ul>
<p><strong>注意</strong>，定义tree结构数组的时候，该数组的大小是maxn*4！注意这里，否认程序会RE;</p>
<h2 id="查询线段树"><a href="#查询线段树" class="headerlink" title="查询线段树"></a>查询线段树</h2><p>已经构建好了线段树，那么怎样在它上面超找某个区间的最小值呢？查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间，因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下，具体见代码解释<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div></pre></td><td class="code"><pre><div class="line">/*</div><div class="line">功能：线段树的区间查询</div><div class="line">root：当前线段树的根节点下标</div><div class="line">[nstart, nend]: 当前节点所表示的区间</div><div class="line">[qstart, qend]: 此次查询的区间</div><div class="line">*/</div><div class="line">int query(int root, int nstart, int nend, int qstart, int qend)</div><div class="line">&#123;</div><div class="line">    //查询区间和当前节点区间没有交集</div><div class="line">    if(qstart &gt; nend || qend &lt; nstart)</div><div class="line">        return INFINITE;</div><div class="line">    //当前节点区间包含在查询区间内</div><div class="line">    if(qstart &lt;= nstart &amp;&amp; qend &gt;= nend)</div><div class="line">        return segTree[root].val;</div><div class="line">    //分别从左右子树查询，返回两者查询结果的较小值</div><div class="line">    int mid = (nstart + nend) / 2;</div><div class="line">    return min(query(root*2+1, nstart, mid, qstart, qend),</div><div class="line">               query(root*2+2, mid + 1, nend, qstart, qend));</div><div class="line"></div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>举例说明（对照上面的二叉树）：<br>1、当我们要查询区间[0,2]的最小值时，从根节点开始，要分别查询左右子树，查询左子树时节点区间[0,2]包含在查询区间[0,2]内，返回当前节点的值1，查询右子树时，节点区间[3,5]和查询区间[0,2]没有交集，返回正无穷INFINITE，查询结果取两子树查询结果的较小值1，因此结果是1.<br>2、查询区间[0,3]时，从根节点开始，查询左子树的节点区间[0,2]包含在区间[0,3]内，返回当前节点的值1；查询右子树时，继续递归查询右子树的左右子树，查询到非叶节点4时，又要继续递归查询：叶子节点4的节点区间[3,3]包含在查询区间[0,3]内，返回4，叶子节点9的节点区间[4,4]和[0,3]没有交集，返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4，叶子节点3的节点区间[5,5]和[0,3]没有交集，返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。</p>
<h2 id="单节点更新"><a href="#单节点更新" class="headerlink" title="单节点更新"></a>单节点更新</h2><p>单节点更新是指只更新线段树的某个叶子节点的值，但是更新叶子节点会对其父节点的值产生影响，因此更新子节点后，要回溯更新其父节点的值。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div></pre></td><td class="code"><pre><div class="line">/*</div><div class="line">功能：更新线段树中某个叶子节点的值</div><div class="line">root：当前线段树的根节点下标</div><div class="line">[nstart, nend]: 当前节点所表示的区间</div><div class="line">index: 待更新节点在原始数组arr中的下标</div><div class="line">addVal: 更新的值（原来的值加上addVal）</div><div class="line">*/</div><div class="line">void updateOne(int root, int nstart, int nend, int index, int addVal)</div><div class="line">&#123;</div><div class="line">    if(nstart == nend)</div><div class="line">    &#123;</div><div class="line">        if(index == nstart)//找到了相应的节点，更新之</div><div class="line">            segTree[root].val += addVal;</div><div class="line">        return;</div><div class="line">    &#125;</div><div class="line">    int mid = (nstart + nend) / 2;</div><div class="line">    if(index &lt;= mid)//在左子树中更新</div><div class="line">        updateOne(root*2+1, nstart, mid, index, addVal);</div><div class="line">    else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新</div><div class="line">    //根据左右子树的值回溯更新当前节点的值</div><div class="line">    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>比如我们要更新叶子节点4（addVal = 6）,更新后值变为10，那么其父节点的值从4变为9，非叶结点3的值更新后不变，根节点更新后也不变。</p>
<h2 id="区间更新"><a href="#区间更新" class="headerlink" title="区间更新"></a>区间更新</h2><p>区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是O(lgn)，例如当我们要更新区间[0,3]内的叶子节点时，需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念，这也是线段树的精华所在。<br>延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。<br>因此需要在线段树结构中加入延迟标记域，本文例子中我们加入标记与addMark，表示节点的子孙节点在原来的值的基础上加上addMark的值，同时还需要修改创建函数build 和 查询函数 query，修改的代码用红色字体表示，其中区间更新的函数为update，代码如下：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div></pre></td><td class="code"><pre><div class="line">const int INFINITE = INT_MAX;</div><div class="line">const int MAXNUM = 1000;</div><div class="line">struct SegTreeNode</div><div class="line">&#123;</div><div class="line">    int val;</div><div class="line">    int addMark;//延迟标记</div><div class="line">&#125;segTree[MAXNUM*20];//定义线段树</div><div class="line"></div><div class="line">/*</div><div class="line">功能：构建线段树</div><div class="line">root：当前线段树的根节点下标</div><div class="line">arr: 用来构造线段树的数组</div><div class="line">istart：数组的起始位置</div><div class="line">iend：数组的结束位置</div><div class="line">*/</div><div class="line">void build(int root, int arr[], int istart, int iend)</div><div class="line">&#123;</div><div class="line">    segTree[root].addMark = 0;//----设置标延迟记域</div><div class="line">    if(istart == iend)//叶子节点</div><div class="line">        segTree[root].val = arr[istart];</div><div class="line">    else</div><div class="line">    &#123;</div><div class="line">        int mid = (istart + iend) / 2;</div><div class="line">        build(root*2+1, arr, istart, mid);//递归构造左子树</div><div class="line">        build(root*2+2, arr, mid+1, iend);//递归构造右子树</div><div class="line">        //根据左右子树根节点的值，更新当前根节点的值</div><div class="line">        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line">/*</div><div class="line">功能：当前节点的标志域向孩子节点传递</div><div class="line">root: 当前线段树的根节点下标</div><div class="line">*/</div><div class="line">void pushDown(int root)</div><div class="line">&#123;</div><div class="line">    if(segTree[root].addMark != 0)</div><div class="line">    &#123;</div><div class="line">        //设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递</div><div class="line">        //所以是 “+=”</div><div class="line">        segTree[root*2+1].addMark += segTree[root].addMark;</div><div class="line">        segTree[root*2+2].addMark += segTree[root].addMark;</div><div class="line">        //根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元</div><div class="line">        //素加上一个值时，区间的最小值也加上这个值</div><div class="line">        segTree[root*2+1].val += segTree[root].addMark;</div><div class="line">        segTree[root*2+2].val += segTree[root].addMark;</div><div class="line">        //传递后，当前节点标记域清空</div><div class="line">        segTree[root].addMark = 0;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line">/*</div><div class="line">功能：线段树的区间查询</div><div class="line">root：当前线段树的根节点下标</div><div class="line">[nstart, nend]: 当前节点所表示的区间</div><div class="line">[qstart, qend]: 此次查询的区间</div><div class="line">*/</div><div class="line">int query(int root, int nstart, int nend, int qstart, int qend)</div><div class="line">&#123;</div><div class="line">    //查询区间和当前节点区间没有交集</div><div class="line">    if(qstart &gt; nend || qend &lt; nstart)</div><div class="line">        return INFINITE;</div><div class="line">    //当前节点区间包含在查询区间内</div><div class="line">    if(qstart &lt;= nstart &amp;&amp; qend &gt;= nend)</div><div class="line">        return segTree[root].val;</div><div class="line">    //分别从左右子树查询，返回两者查询结果的较小值</div><div class="line">    pushDown(root); //----延迟标志域向下传递</div><div class="line">    int mid = (nstart + nend) / 2;</div><div class="line">    return min(query(root*2+1, nstart, mid, qstart, qend),</div><div class="line">               query(root*2+2, mid + 1, nend, qstart, qend));</div><div class="line"></div><div class="line">&#125;</div><div class="line"></div><div class="line">/*</div><div class="line">功能：更新线段树中某个区间内叶子节点的值</div><div class="line">root：当前线段树的根节点下标</div><div class="line">[nstart, nend]: 当前节点所表示的区间</div><div class="line">[ustart, uend]: 待更新的区间</div><div class="line">addVal: 更新的值（原来的值加上addVal）</div><div class="line">*/</div><div class="line">void update(int root, int nstart, int nend, int ustart, int uend, int addVal)</div><div class="line">&#123;</div><div class="line">    //更新区间和当前节点区间没有交集</div><div class="line">    if(ustart &gt; nend || uend &lt; nstart)</div><div class="line">        return ;</div><div class="line">    //当前节点区间包含在更新区间内</div><div class="line">    if(ustart &lt;= nstart &amp;&amp; uend &gt;= nend)</div><div class="line">    &#123;</div><div class="line">        segTree[root].addMark += addVal;</div><div class="line">        segTree[root].val += addVal;</div><div class="line">        return ;</div><div class="line">    &#125;</div><div class="line">    pushDown(root); //延迟标记向下传递</div><div class="line">    //更新左右孩子节点</div><div class="line">    int mid = (nstart + nend) / 2;</div><div class="line">    update(root*2+1, nstart, mid, ustart, uend, addVal);</div><div class="line">    update(root*2+2, mid+1, nend, ustart, uend, addVal);</div><div class="line">    //根据左右子树的值回溯更新当前节点的值</div><div class="line">    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>区间更新举例说明：当我们要对区间[0,2]的叶子节点增加2，利用区间查询的方法从根节点开始找到了非叶子节点[0-2]，把它的值设置为1+2 = 3，并且把它的延迟标记设置为2，更新完毕；当我们要查询区间[0,1]内的最小值时，查找到区间[0,2]时，发现它的标记不为0，并且还要向下搜索，因此要把标记向下传递，把节点[0-1]的值设置为2+2 = 4，标记设置为2，节点[2-2]的值设置为1+2 = 3，标记设置为2（其实叶子节点的标志是不起作用的，这里是为了操作的一致性），然后返回查询结果：[0-1]节点的值4；当我们再次更新区间[0,1]（增加3）时，查询到节点[0-1],发现它的标记值为2，因此把它的标记值设置为2+3 = 5，节点的值设置为4+3 = 7；<br>其实当区间更新的区间左右值相等时（[i,i]），就相当于单节点更新，单节点更新只是区间更新的特例。</p>
<h1 id="线段树实战"><a href="#线段树实战" class="headerlink" title="线段树实战"></a>线段树实战</h1><p>之后的几篇文章会通过acm的一些题目来运用线段树</p>
<h1 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h1><p>[GeeksforGeeks] (<a href="http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/" target="_blank" rel="external">http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/</a>)<br><a href="http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/" target="_blank" rel="external">GeeksforGeeks</a><br>懂得博客<a href="http://dongxicheng.org/structure/segment-tree/" target="_blank" rel="external">数据结构之线段树</a><br>MetaSeed<a href="http://blog.csdn.net/metalseed/article/details/8039326" target="_blank" rel="external">数据结构专题—线段树</a><br>otOnlySuccess<a href="http://www.notonlysuccess.com/index.php/segment-tree-complete/" target="_blank" rel="external">完全版 线段树</a></p>

      
    </div>
    
  </div>
  
    
    <div class="copyright">
        <p><span>本文标题:</span><a href="/2015/08/13/线段树学习笔记/">线段树学习笔记-1-入门</a></p>
        <p><span>文章作者:</span><a href="/" title="回到主页">Bingo</a></p>
        <p><span>发布时间:</span>2015-08-13, 10:15:15</p>
        <p><span>最后更新:</span>2015-11-25, 11:08:41</p>
        <p>
            <span>原始链接:</span><a class="post-url" href="/2015/08/13/线段树学习笔记/" title="线段树学习笔记-1-入门">http://blog.acbingo.cn/2015/08/13/线段树学习笔记/</a>
            <span class="copy-path" data-clipboard-text="原文: http://blog.acbingo.cn/2015/08/13/线段树学习笔记/　　作者: Bingo" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span>
            <script> var clipboard = new Clipboard('.copy-path'); </script>
        </p>
        <p>
            <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
        </p>
    </div>



    <nav id="article-nav">
        
            <div id="article-nav-newer" class="article-nav-title">
                <a href="/2015/08/13/线段树学习笔记-2-hdu1166/">
                    线段树学习笔记-2-hdu1166
                </a>
            </div>
        
        
            <div id="article-nav-older" class="article-nav-title">
                <a href="/2015/08/11/Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试/">
                    Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试
                </a>
            </div>
        
    </nav>

  
</article>

    <div id="toc" class="toc-article">
        <strong class="toc-title">文章目录</strong>
        
            <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#概述"><span class="toc-number">1.</span> <span class="toc-text">概述</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#从一个例子理解线段树"><span class="toc-number">2.</span> <span class="toc-text">从一个例子理解线段树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#创建线段树"><span class="toc-number">2.1.</span> <span class="toc-text">创建线段树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#查询线段树"><span class="toc-number">2.2.</span> <span class="toc-text">查询线段树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#单节点更新"><span class="toc-number">2.3.</span> <span class="toc-text">单节点更新</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#区间更新"><span class="toc-number">2.4.</span> <span class="toc-text">区间更新</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#线段树实战"><span class="toc-number">3.</span> <span class="toc-text">线段树实战</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#参考"><span class="toc-number">4.</span> <span class="toc-text">参考</span></a></li></ol>
        
    </div>
    <style>
        .left-col .switch-btn,
        .left-col .switch-area {
            display: none;
        }
        .toc-level-3 i,
        .toc-level-3 ol {
            display: none !important;
        }
    </style>

    <input type="button" id="tocButton" value="隐藏目录"  title="点击按钮隐藏或者显示文章目录">

    <script>
        yiliaConfig.toc = ["隐藏目录", "显示目录", !!"false"];
    </script>



    
<div class="share">
    
        <div class="bdsharebuttonbox">
            <a href="#" class="fa fa-twitter bds_twi" data-cmd="twi" title="分享到推特"></a>
            <a href="#" class="fa fa-weibo bds_tsina" data-cmd="tsina" title="分享到新浪微博"></a>
            <a href="#" class="fa fa-qq bds_sqq" data-cmd="sqq" title="分享给 QQ 好友"></a>
            <a href="#" class="fa fa-files-o bds_copy" data-cmd="copy" title="复制网址"></a>
            <a href="#" class="fa fa fa-envelope-o bds_mail" data-cmd="mail" title="通过邮件分享"></a>
            <a href="#" class="fa fa-weixin bds_weixin" data-cmd="weixin" title="生成文章二维码"></a>
            <a href="#" class="fa fa-share-alt bds_more" data-cmd="more"></i></a>
        </div>
        <script>
            window._bd_share_config={
                "common":{"bdSnsKey":{},"bdText":"线段树学习笔记-1-入门　| Bingo's Blog　","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
        </script>
    

    
</div>







    
      <div class="duoshuo" id="comments">
    <div id="comment-box" ></div>
    <div class="ds-thread" id="ds-thread" data-thread-key="2015/08/13/线段树学习笔记/" data-title="线段树学习笔记-1-入门" data-url="http://blog.acbingo.cn/2015/08/13/线段树学习笔记/"></div>
    <script>
        var duoshuoQuery = {short_name:"acbingo"};
        var loadComment = function(){
            var d = document, s = d.createElement('script');
            s.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
            s.async = true; s.charset = 'UTF-8';
            (d.head || d.body).appendChild(s);
        }

        
    </script>
    
    <script> loadComment(); </script>

</div>
    




    <div class="scroll" id="post-nav-button">
        
            <a href="/2015/08/13/线段树学习笔记-2-hdu1166/" title="上一篇: 线段树学习笔记-2-hdu1166">
                <i class="fa fa-angle-left"></i>
            </a>
        

        <a title="文章列表"><i class="fa fa-bars"></i><i class="fa fa-times"></i></a>

        
            <a href="/2015/08/11/Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试/" title="下一篇: Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试">
                <i class="fa fa-angle-right"></i>
            </a>
        
    </div>

    <ul class="post-list"><li class="post-list-item"><a class="post-list-link" href="/2016/08/07/c++初始化列表/">c++初始化列表</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/05/一步一步学习红黑树-2/">一步一步学习红黑树-2</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/04/一步一步学习红黑树/">一步一步学习红黑树-1</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/回文解码/">回文解码</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/C++中虚析构函数的作用/">C++中虚析构函数的作用</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/const/">const</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/const与常成员函数/">const与常成员函数</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/31/虚拟继承/">虚拟继承</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/31/函数指针/">函数指针</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/记事本/">记事本</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/StarFiles/">StarFiles</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/酒店管理系统/">酒店管理系统</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/飞机大战/">飞机大战</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/27/仿函数/">仿函数/函数对象</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/27/二叉树中和为某一值的路径/">二叉树中和为某一值的路径</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/递归实现反转列表/">递归实现反转链表</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/快速幂/">快速幂</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/bitset的用法/">bitset的用法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/二分查找、归并排序和快速排序/">二分查找、归并排序和快速排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/25/重建二叉树/">重建二叉树</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/25/leetcode_5/">LeetCode_5:Longest Palindromic Substring</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_4/">LeetCode_4:Median of Two Sorted Arrays</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_3/">LeetCode_3:Longest Substring Without Repeating Characters</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_2/">LeetCode_2:Add Two Numbers</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_1_Two Sum/">LeetCode_1:Two Sum</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/06/07/Bingo's_ShadowSocks使用说明/">Bingo's_Shadowsocks</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/03/如何优雅的开启wifi热点/">如何优雅的开启wifi热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/02/如何优雅的连接指定wifi热点/">如何优雅的连接指定wifi热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/02/对AndroidWifi状态广播的研究/">对AndroidWifi状态广播的研究</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/01/coursera数据结构_字符串_课后作业/">coursera数据结构_字符串_课后作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/01/简单几步在Android_Studio上实现二维码的扫描/">简单几步在Android_Studio上实现二维码的生成与扫描</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/25/coursera_算法课后习题/">coursera_算法课后习题</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/25/coursera_计算机组成学习笔记/">coursera_计算机组成学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/20/cocos2dx-飞机大战/">cocos2dx-飞机大战</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/14/android_ping不通电脑/">android_ping不通电脑</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/14/android创建与连接热点/">android创建与连接热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/01/coursera_算法_递归/">coursera_算法_递归</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/30/coursera_操作系统学习笔记/">coursera_操作系统学习笔记_计算机操作系统概述</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/29/编译原理_中科大公开课_第一单元编译器介绍作业/">编译原理_中科大公开课_第一单元编译器介绍作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/25/关于Inflater与findViewById()的思考/">关于Inflater与findViewById()的思考</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/11/coursera_魔兽世界终结版/">coursera_魔兽世界终结版</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/05/coursera_算法作业_枚举/">coursera_算法作业_枚举</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/27/coursera_c++高级主体和c++11新特性/">coursera_c++高级主体和c++11新特性</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/27/coursera_c++期末考试/">coursera_c++期末考试</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/24/coursera_STL2作业/">coursera_STL2作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/21/coursera容器适配器/">coursera容器适配器_算法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/21/coursera标准模版库STL2/">coursera标准模版库STL2</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/20/coursera编程作业-STL1/">coursera编程作业-STL1</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/20/coursera疑问/">coursera疑问</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/19/coursera学习笔记-函数对象/">coursera学习笔记-函数对象</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/19/coursera学习笔记-顺序容器Vector/">coursera学习笔记-顺序容器Vector、List和Deque</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/05/算法学习笔记-14-最长公共子序列/">算法学习笔记-14-最长公共子序列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/03/算法学习笔记-13-矩阵连乘问题/">算法学习笔记-13-矩阵连乘问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-12-循环赛日程表/">算法学习笔记-12-循环赛日程表</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-11-最接近点对问题/">算法学习笔记-11-最接近点对问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-10-线性时间选择/">算法学习笔记-10-线性时间选择</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/27/算法学习笔记-9-快速排序/">算法学习笔记-9-快速排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/26/算法学习笔记-8-合并排序/">算法学习笔记-8-归并排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/24/算法学习笔记-7-棋盘覆盖问题/">算法学习笔记-7-棋盘覆盖问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/22/算法学习笔记-6-Strassen矩阵乘法/">算法学习笔记-6-Strassen矩阵乘法</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/21/算法学习笔记-5-Hanoi塔问题/">算法学习笔记-5-Hanoi塔问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/20/算法学习笔记-4-整数划分问题/">算法学习笔记-4-整数划分问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/19/算法学习笔记-3-排列问题/">算法学习笔记-3-排列问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/18/算法学习笔记-2-递归的概念/">算法学习笔记-2-递归的概念</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/coursera_标准模板库STL/">coursera_标准模板库STL</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/算法学习笔记-0-序/">算法学习笔记-0-序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/算法学习笔记-1-NP完全性理论/">算法学习笔记-1-NP完全性理论</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/14/文件操作和模板_编程作业/">文件操作和模板_编程作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/11/ubuntu下安装最新的nodejs(v4.2.2)/">ubuntu下安装最新的nodejs(v4.2.2)</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/11/ubuntu14.04的环境变量/">ubuntu14.04的环境变量</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/01/coursera学习笔记_文件操作和模板/">coursera学习笔记_文件操作和模板</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/31/coursera学习笔记_多态和虚函数/">coursera学习笔记_多态和虚函数</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/28/Coursera_程序设计与晋级_继承与派生_编程作业/">Coursera_程序设计与晋级_继承与派生_编程作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/22/科大OJ-数据结构-DNA序列/">科大OJ-数据结构-DNA序列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/20/科大OJ-数据结构-求表达式串的后缀表达式和值/">科大OJ-数据结构-求表达式串的后缀表达式和值</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/01/科大OJ-数据结构-击鼓传花/">科大OJ-数据结构-击鼓传花</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/30/科大OJ-数据结构-求集合的交并补集/">科大OJ-数据结构-求集合的交并补集</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/27/hexo无法本地访问/">hexo无法本地访问</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/26/继承与派生/">coursera学习笔记_继承与派生</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/26/大数类模板/">大数类模板</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/15/vimium学习笔记/">vimium学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/04/程序员矩阵/">程序员矩阵</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/03/coursera学习笔记_运算符重载/">coursera学习笔记_运算符重载</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/01/写hexo博客、markdown文章时图床的挑选/">写hexo博客、markdown文章时图床的挑选</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/31/coursera学习笔记-c++程序设计/">coursera学习笔记-c++程序设计</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/29/Linux下C语言应用编程学习笔记/">Linux下C语言应用编程学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/28/linux学习笔记2/">linux学习笔记2</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/Bingo's exVim/">Bingo的VIM</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/linux下去掉^M的方法/">linux下去掉^M的方法</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/vim的持久撤销功能/">vim的持久撤销功能</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/25/linux学习笔记/">linux学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-7-hdu1698/">线段树学习笔记-7-hdu1698</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-6-区间更新/">线段树学习笔记-6-区间更新</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/Coursera_程序设计与算法_C程序设计进阶/">Coursera_程序设计与算法_C程序设计进阶</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-5-hdu2795/">线段树学习笔记-5-hdu2795</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/线段树学习笔记-4-hdu1394/">线段树学习笔记-4-hdu1394</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/求逆序对的个数/">求逆序对的个数</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/线段树学习笔记-3-hdu1754/">线段树学习笔记-3-hdu1754</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/13/线段树学习笔记-2-hdu1166/">线段树学习笔记-2-hdu1166</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/13/线段树学习笔记/">线段树学习笔记-1-入门</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/11/Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试/">Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/Coursera_程序设计与算法_C程序设计进阶_C程序中的函数/">Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习/">Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/hdu4821 String/">hdu4821 String</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/09/Rolling Hash(Rabin-Karp算法)匹配字符串/">Rolling Hash(Rabin-Karp算法)匹配字符串</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/09/设置vim的默认工作路径/">设置vim的默认工作路径</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/08/滑动窗口的单调队列/">滑动窗口的单调队列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/08/ssh -T git@github.com出现Permission denied (publickey)/">ssh -T git@github.com出现Permission denied (publickey)</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/05/29/UVa10791-Minimum-Sum-LCM/">UVa10791-Minimum Sum LCM</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/05/29/uva100/">uva100</a></li></ul>




    <script>
        
    </script>
</div>
      <footer id="footer">
    <div class="outer">
        <div id="footer-info">
            <div class="footer-left">
                <i class="fa fa-copyright"></i> 
                2014-2016 Bingo
            </div>
            <div class="footer-right">
                <a href="http://hexo.io/" target="_blank" title="快速、简洁且高效的博客框架">Hexo</a>  Theme <a href="https://github.com/MOxFIVE/hexo-theme-yelee" target="_blank" title="简而不减 Hexo 双栏博客主题  v3.5">Yelee</a> by MOxFIVE <i class="fa fa-heart animated infinite pulse"></i>
            </div>
        </div>
        
            <div class="visit">
                
                    <span id="busuanzi_container_site_pv" style='display:none'>
                        <span id="site-visit" title="本站到访数"><i class="fa fa-user" aria-hidden="true"></i><span id="busuanzi_value_site_uv"></span>
                        </span>
                    </span>
                
                
                    <span>| </span>
                
                
                    <span id="busuanzi_container_page_pv" style='display:none'>
                        <span id="page-visit"  title="本页阅读量"><i class="fa fa-eye animated infinite pulse" aria-hidden="true"></i><span id="busuanzi_value_page_pv"></span>
                        </span>
                    </span>
                
            </div>
        
    </div>
</footer>
    </div>
    
<script data-main="/js/main.js" src="//cdn.bootcss.com/require.js/2.2.0/require.min.js"></script>





<div class="scroll" id="scroll">
    <a href="#" title="返回顶部"><i class="fa fa-arrow-up"></i></a>
    <a href="#comments" onclick="load$hide();" title="查看评论"><i class="fa fa-comments-o"></i></a>
    <a href="#footer" title="转到底部"><i class="fa fa-arrow-down"></i></a>
</div>
<script>
    // Open in New Window
    
        var oOpenInNew = {
            
            
            
            
            
            
             archives: ".archive-article-title", 
             miniArchives: "a.post-list-link", 
            
             friends: "#js-friends a", 
             socail: ".social a" 
        }
        for (var x in oOpenInNew) {
            $(oOpenInNew[x]).attr("target", "_blank");
        }
    
</script>

<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js">
</script>
  </div>
</body>
</html>